package demo1;


import javafx.scene.chart.ScatterChart;

public class SingleLinkedList {
     class Singlelist {
      public int val;
     public Singlelist next;

          public Singlelist(int val) {
               this.val = val;
          }

     }

     public Singlelist head;
     public void MyLinkedlist() {
          Singlelist node1 = new Singlelist(1);
          Singlelist node2 = new Singlelist(2);
          Singlelist node3 = new Singlelist(3);
          Singlelist node4 = new Singlelist(4);
          Singlelist node5 = new Singlelist(5);

          node1.next = node2;
          node2.next = node3;
          node3.next = node4;
          node4.next = node5;

          this.head = node1;

     }

     //头插法
     public void addFirst(int data){
          Singlelist cur = this.head;
          Singlelist node = new Singlelist(data);
          node.next = cur;
          this.head = node;
     }

     //尾插法
     public void addLast(int data){
          Singlelist cur = this.head;
          Singlelist node = new Singlelist(data);

          if (cur == null) {
               this.head = node;
               return;
          }
          while(cur.next != null){
               cur = cur.next;
          }
          cur = node;
     }

     //任意位置插入,第一个数据节点为0号下标

     public void addIndex(int index,int data){

          if(index < 0 || index > size()) {
               System.out.println("超出了这个范围");
          }

          if(index == 0) {
               addFirst(data);
          }

          if (index == size()) {
               addLast(data);
          }

          Singlelist cur = searchPrev(index);
          Singlelist node = new Singlelist(data);
          node.next = cur.next;
          cur.next =node;
     }

     private Singlelist searchPrev (int index) {

          Singlelist cur = this.head;
          while(index -1 != 0) {
               cur = cur.next;
               index--;
          }
          return cur;
     }

     //查找是否包含关键字key是否在单链表当中
     public boolean contains(int key){
          Singlelist cur = this.head;

          while (cur != null) {
               if (cur.val == key) {
                  return true;
               }
               cur = cur.next;
          }

          return false;
     }

     //删除第一次出现关键字为key的节点
     public void remove(int key) {

          if(this.head.val == key ) {
               this.head = this.head.next;
               return ;
          }

          // 1.找到前驱
          Singlelist cur = findPrev(key);
          // 2.判断赋值是否为空
          if (cur == null) {
               System.out.println("没有你要删除的数字");
               return;
          }
          // 3.删除
          Singlelist del = cur.next;
          cur.next = del.next;
     }
     /**
      * 找到key关键字前一个节点所在位置
      * @param key
      * @return
      * */
     private Singlelist findPrev (int key) {



          Singlelist cur = this.head;
          while ( cur.next != null ) {
               if(cur.next.val == key) {
                   return cur;
               }
               cur = cur.next;
          }

          return null;
     }
     //删除所有值为key的节点
     public void removeAllKey(int key){
          if (this.head == null) {
               return;
          }

          Singlelist prev = head;
          Singlelist cur = head.next;
          while(cur != null) {
               if (cur.val == key) {
                    prev.next = cur.next;
                    cur = cur.next;
               }else{
                    prev = cur;
                    cur = cur.next;
               }
          }
          if (head.val == key) {
               head = head.next;
          }
     }

     //得到单链表的长度
     public int size(){
          int flg = 0;
          Singlelist cur = this.head;
          while(cur != null){
              flg++;
              cur = cur.next;
          }
          return flg;
     }

     public void display(){
          Singlelist cur = this.head;
          while(cur != null){
               System.out.println(cur.val);
               cur = cur.next;
          }
     }
     public void clear(){
          Singlelist cur = this.head;
         while(cur != null){
              Singlelist Cur = cur.next;
              cur.val = 0;
              cur.next = null;
              cur = Cur;
         }
         head = null;
     }
 }